1. Field of the Invention
The present invention generally relates to computer systems, and more particularly to a method of indexing memory addresses in a computer program file.
2. Description of the Related Art
The basic structure of a conventional computer system 10 is shown in FIG. 1. The heart of computer system 10 is a central processing unit (CPU) or processor 12 which is connected to several peripheral devices, including input/output (I/0) devices 14 (such as a display monitor and keyboard) for the user interface, a permanent memory device 16 (such as a hard disk or floppy diskette) for storing the computer's operating system and user programs, and a temporary memory device 18 (such as random access memory or RAM) that is used by processor 12 to carry out program instructions. Processor 12 communicates with the peripheral devices by various means, including a bus 20 or a direct channel 22. Computer system 10 may have many additional components which are not shown, such as serial and parallel ports for connection to, e.g., modems or printers. Those skilled in the art will further appreciate that there are other components that might be used in conjunction with those shown in the block diagram of FIG. 1; for example, a display adapter connected to processor 12 might be used to control a video display monitor, and a memory controller may be used as an interface between temporary memory device 18 and processor 12. Computer system 10 also includes firmware 24 whose primary purpose is to seek out and load an operating system from one of the peripherals (usually permanent memory device 16) whenever the computer is first turned on.
With further reference to FIG. 2, when a user program runs on a computer, the computer's operating system (OS) first loads the main program file 26 into temporary memory 18. Program file 26 includes several objects (values) stored as data or text, and instructions for handling the data and other parameters which may be input during program execution. Processor 12 uses "logical addresses" to access the file objects, and these logical addresses correspond to physical addresses in RAM 18. "Binding" of instructions and data to physical memory addresses is accomplished by compiling the program file using relocatable code, which is indexed (linked) to physical memory by the OS loader during loading of the file. Thus, even though the address space of memory 18 begins at location zero, the first address of the user program is not necessarily zero, which allows a user process to reside in any part of physical memory.
The data and instructions in a given file are usually divided up into "pages" which are sized to fit more efficiently in memory 18. As processes are loaded and removed from memory, the free areas of memory space becomes broken up, or fragmented. Often there is enough free memory to load a process, but the free memory is not contiguous. Paging allows a process to occupy such non-contiguous memory spaces. A logical address is then divided into two parts: a page number and a page offset. The page number is indexed in a page table which contains the base address of each page in physical memory, and this base address is combined with the page offset to determine the actual physical memory address of the object. The size of a page depends upon the particular hardware platform, with a 2 or 4 kilobyte (KB) size being common.
If a program is particularly complicated, or if it requires a large amount of data or text, it is desirable to break up the program into multiple files so as to obtain better memory space utilization. One such approach involves the use of dynamically linked libraries (DLLs). The main program file 26 which is always loaded first for a particular user program is referred to as an "executable" file. The executable file can then call routines in DLL files 28 and 30. A "stub" is included in the executable file for each DLL routine reference. When the routine is called, the stub replaces itself with the address of the routine in the newly loaded DLL file. In this manner, all processes that require a particular library routine use only one copy of the library code, eliminating duplication of the library on both the hard disk 16 as well as in main memory 18. The use of DLLs has other advantages, such as easy library updating (e.g., for bug fixes). Without dynamic linking, all programs referencing the library would need to be relinked to use the updated library, but this is not required with a DLL since linking is postponed until execution time.
References between objects within a single DLL or executable file are problematic because the linker cannot determine the run time addresses of these objects unless they have been based. As a result, the linker deposits internal "fixup" records 32, 34, 36 within the executable or DLL file image. The OS loader is then responsible for reading the fixup records at load time and applying the necessary fixup information as individual DLL or executable pages are paged-in. Internal fixups can be removed from the fixup section of these files (referred to as LX files) if the executable or DLL file is based, i.e., marked to be loaded at a specific virtual address. Unfortunately, the DLL or executable file cannot be so loaded if the specified virtual address is unavailable (i.e., another file has already been loaded at that address). Very few DLL files are based because they are usually loaded at shared addresses. Many executables are based because they can be loaded at private virtual addresses. In addition to internal fixups, there are also external fixups. External fixups pertain to references spanning multiple DLLs and/or executables.
Internal fixups are read in at load time and stored in a pageable kernel data structure. Fixup sections of LX files can be quite large, typically 20 KB to 100 KB, but fixup records as large as 750 KB are not unheard of. This size is clearly undesirable as it increases permanent memory space requirements as well as complicating memory management. In addition to being read in at load time, the pageable fixup structures are indexed each time a corresponding page is faulted into memory. The indexing of these structures can result in page faults and increases the overall system working set. It would, therefore, be desirable and advantageous to devise a method of indexing memory address information in LX files without using excessively large fixup records.